package com.leetcode_Onequestion;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @Author jsh
 * @Date 2023/3/11 23:49
 * @Version 1.0
 */
/*
* 给定一个放有字母和数字的数组，找到最长的子数组，且包含的字母和数字的个数相同。

返回该子数组，若存在多个最长子数组，返回左端点下标值最小的子数组。若不存在这样的数组，返回一个空数组。

示例 1:

输入: ["A","1","B","C","D","2","3","4","E","5","F","G","6","7","H","I","J","K","L","M"]

输出: ["A","1","B","C","D","2","3","4","E","5","F","G","6","7"]
示例 2:

输入: ["A","A"]

输出: []
提示：

array.length <= 100000

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-longest-subarray-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*
* */
public class leetcode_17_05 {

    public static void main(String[] args) {

        System.out.println(Character.isDigit("O".charAt(0)));
        String d[] = {"42","10","O","t","y","p","g","B","96","H","5","v","P","52","25","96",
                "b","L","Y","z","d","52","3","v","71","J","A","0","v","51","E","k","H","96",
                "21","W","59","I","V","s","59","w","X","33","29","H","32","51","f","i","58",
                "56","66","90","F","10","93","53","85","28","78","d","67","81","T","K","S",
                "l","L","Z","j","5","R","b","44","R","h","B","30","63","z","75","60","m","61",
                "a","5","S","Z","D","2","A","W","k","84","44","96","96","y","M"};
        String[] longestSubarray2 = findLongestSubarray2(d);

        System.out.println(longestSubarray2.length);

        for (String s : longestSubarray2){
            System.out.print(s + ",");
        }

        //System.out.println("abcd".substring(0, 1));
        //char[] chars = "abcdefg".toCharArray();
        //System.out.println(Character.isDigit("zx".charAt(0)));


        //System.out.println(Arrays.copyOfRange(chars, 0, 1).length);
        String[] s =
                {"10","O","t","y","p","g","B","96","H","5","v",
                        "P","52","25","96","b","L","Y","z","d","52",
                        "3","v","71","J","A","0","v","51","E","k",
                        "H","96","21","W","59","I","V","s","59",
                        "w","X","33","29","H","32","51","f","i",
                        "58","56","66","90","F","10","93","53",
                        "85","28","78","d","67","81","T","K"};
    }

    /* @Author cxx
    * @date 23:08 2023/3/13
    * @Param
    * @return
    **/
    public static String[] findLongestSubarray2(String[] array) {
        Map<Integer, Integer> map = new HashMap<>();

        map.put(0, -1);
        int sum = 0;
        int l = 0, r = 0;
        int length = 0;
        for (int i = 0; i < array.length; i++) {
            sum += Character.isDigit(array[i].charAt(0)) ? 1 : -1;

            System.out.print(sum+",");
            if (map.containsKey(sum) && i - map.get(sum) > length ){
                l = map.get(sum);
                r = i;
                length = r - l;

                //System.out.println("sum:"+sum);
                //System.out.println("length:" + length);
            }else {
                map.put(sum, i);
            }
        }

/*        if (r == 0)
            r = l -1;*/
        //System.out.println(l+","+r);
        return Arrays.copyOfRange(array,l+1,r+1);
    }


    public String[] findLongestSubarray(String[] array) {

        Map<Integer,Integer> map = new HashMap<>();
        int x = 0, left = 0, right = 0, l = 0 ;
        map.put(0,-1);
        for (int i = 0; i < array.length; i++) {

            //计算前缀数字与字母数的差值
            x += Character.isDigit(array[i].charAt(0)) ? 1 : -1;

            if(map.containsKey(x)&& i - map.get(x)> l){
                left = map.get(x)+1;
                right = i+1;
                l = right -left;
            }else {
                map.put(x,i);
            }

        }
        //System.arraycopy();
        if (right == 0)
            return new String[0];
        return Arrays.copyOfRange(array,left,right);
    }
}
